home
***
CD-ROM
|
disk
|
FTP
|
other
***
search
/
Amiga Collections: Camelot
/
Camelot 078 (1990-06)(Swedish User Group of Amiga)(SE)(PD)[WB].zip
/
Camelot 078 (1990-06)(Swedish User Group of Amiga)(SE)(PD)[WB].adf
/
fassem
/
quick.a
< prev
next >
Wrap
Text File
|
1990-05-06
|
12KB
|
268 lines
*************************************************************************
* This routine can be used to demostrate FASSEM. To assemble, do: *
* *
* fassem.demo quick.a -oquick.o (For an object file) *
* fassem.demo quick.a -oquick.o -lram:x (For a listing) *
* fassem.demo quick.a -oquick.o -cx (For a cross reference) *
* fassem.demo >ram:x quick.a -cx (Cross ref to a file) *
* fassem.demo quick.a -cn (Kill the demo message) *
* fassem.demo quick.a -dFASSEM (Use IS and UNDEF code) *
* fassem.demo quick.a -dERROR (Show error from xdef) *
* *
* The above options may be combined. *
*************************************************************************
*************************************************************************
* QUICKSORT ROUTINE (c) 1990 Edward Lappin, all rights reserved. *
* From: Sorting and Searching by Knuth, pages 116-117. *
* *
* int sort(mainarray,tagarray,length) *
* Sort the main array in order of lower to higher values. *
* The tagarray is used to keep track of where the data was moved. *
* Inputs: mainarray - pointer to first index of the main data. When *
* (long *) sorted, mainarray[0] will have the smallest *
* value and mainarray[length-1] will have the *
* largest value. IMPORTANT: the array MUST have *
* two extra locations: mainarray[-1] must exist *
* and mainarray[length] must exist. These are *
* used to increase the efficiency of the algorithm*
* tagarray - These are tags associated with the mainarray *
* (long *) data. If the data in mainarray is swapped, the *
* tag data is also swapped. This allows identi- *
* fication of the data when sorted. *
* length - # of entries to sort. Must be 1 to 65533. *
* Outputs: sort - # of swaps done (somewhat fudged). *
*************************************************************************
*************************************************************************
* The following variables are used internally: *
* a0 - ptr to start of the main array. *
* a1 - (tagarray-mainarray). This is added into a pointer into *
* the mainarray to get a location in tagarray. *
* a2 - Scan ptr i (into the mainarray). *
* a3 - Scan ptr j (into the mainarray). *
* a4 - Stack for the quicksort partitions left to do. When this *
* equals sp, the stack is empty. We push the left boundary*
* first, then the right. Both are ptrs into mainarray. *
* a5 - Left boundary of current working partition (mainarray ptr)*
* d0 - Current compare value. *
* d1 - Swap value location. *
* d2 - Compare location. *
* d3 - Right boundary of current partition (mainarray ptr). *
* d4 - Smallest size to do quicksort partition on (mult by size) *
* d5 - Swap counter. *
*************************************************************************
SMALLINT equ $80000000 Min and max compare values
LARGEINT equ $7FFFFFFF
SMALLLIMIT equ 9 Min partition size for sort
thesize equ 4 Bytes for key or tag element
multtag macro Parameter is reg to mult by tagsize
ifne thesize-4
fail <tag size does not match code>
endc
add.l \1,\1
add.l \1,\1
endm
*
* The following are defined first using equ and reg
*
saveregsp equ 8*4 Bytes used on stack to save registers
saveregs reg a2-a5/d2-d5
mainarray equ saveregsp+4
tagarray equ saveregsp+8
length equ saveregsp+12
*
* The IS directive can be used with FASSEM to assign any text. To reuse
*the symbol names, it is necessary to undefine them.
*
ifd FASSEM
undef saveregsp,saveregs,mainarray,tagarray,length
saveregsp is 8*4 Bytes used on stack to save registers
saveregs is a2-a5/d2-d5
mainarray is saveregsp+4
tagarray is saveregsp+8
length is saveregsp+12
endc
_sort equ *
movem.l saveregs,-(sp)
moveq #0,d5
move.l mainarray(sp),a0
move.l tagarray(sp),a1
suba.l a0,a1 Want tag-main in a1
moveq #SMALLLIMIT*thesize,d4
*
* Check to see if we have enough elements to quicksort and set initial
*partition.
*
Q1 move.l length(sp),d1
multtag d1 Convert length to offset bytes
move.l #SMALLINT,-thesize(a0) Set limit markers
move.l #LARGEINT,0(a0,d1.l)
cmp.l d4,d1
bls Q9 If not big enough, skip
move.l sp,a4 Initialize partition stack
move.l a0,a5 Set left limit
move.l d1,d3
subq.l #thesize,d3
add.l a0,d3 Set right limit
*
* Setup to check the partition from a5 (l) to d3 (r). We will see if we
*need to create a new partition or just swap.
*
Q2 lea thesize(a5),a2 Set left to right scan (i) to l+1
move.l d3,a3
addq.l #thesize,a3 Set right to left scan (j) to r+1
move.l (a5),d0 Set d0 (K) to mainarray[l]
*
* Scan from left to right, then right to left.
*
Q3 cmp.l (a2)+,d0
bgt Q3
subq.l #thesize,a2 Convert back to point to last compare
Q4 cmp.l -(a3),d0
blt Q4
Q5 cmp.l a2,a3
bls.s Q7 If j <= i, we will use the stack
*
* This is the case of j > i after the scan. We only need to swap the
*locations of i and j.
*
Q6 move.l 0(a2,a1.l),d1
move.l 0(a3,a1.l),0(a2,a1.l)
move.l d1,0(a3,a1.l) The tags are swapped
move.l (a2),d1
move.l (a3),(a2)+ We want to increase i by 1
move.l d1,(a3) The mainarray keys are swapped
addq.l #1,d5
bra Q3
*
* This is the case of j <= i after the scan. We want to swap l and j.
*Then, we need to determine if a partition needs to be split and put on the
*stack.
Q7 move.l (a5),d1
move.l (a3),(a5)
move.l d1,(a3) The mainarray keys are swapped
move.l 0(a5,a1.l),d1
move.l 0(a3,a1.l),0(a5,a1.l)
move.l d1,0(a3,a1.l) The tags are swapped
addq.l #1,d5
move.l d3,d1
sub.l a3,d1 r-j
move.l a3,d2
sub.l a5,d2 j-l
cmp.l d1,d2
bhi chkother
*
* This is the case of r-j >= j-l. Check to see if j-l > M. If so, we
*will create a new partition and place on the stack.
*
cmp.l d4,d2
ble.s smalljl
pea thesize(a3) j+1 - partition to do later
move.l d3,-(sp) r
move.l a3,d3
subq.l #thesize,d3 Set r = j-1
bra Q2 Continue scan
smalljl cmp.l d4,d1
ble.s Q8
*
* This is the case of r-j > M >= j-l. We want to start a new scan.
*
lea 4(a3),a5 Set l = j+1
bra Q2
*
* This is the case of j-l > r-j. Check to see if r-j > M. If so, new
*partition.
*
chkother cmp.l d4,d1
ble.s smallrj
move.l a5,-(sp) l - partition to do later
pea -thesize(a3) j-1
lea thesize(a3),a5 Set l = j+1
bra Q2 Continue scan
smallrj cmp.l d4,d2
ble.s Q8
*
* This is the case of j-l > M >= r-j. We want to start a new scan.
*
move.l a3,d3
subq.l #thesize,d3 Set r = j-1
bra Q2
*
* We are done with the current partition. See if there are any on the
*stack. If so, use the top one. If not, we are done with partitioning.
*
Q8 cmp.l a4,sp Check cc (same as High or Same)
bcc Q9 We are done since empty stack
move.l (sp)+,d3 Get r from stack
move.l (sp)+,a5 Get l from stack
bra Q2 Start the new scan
*
* At this point, we need to do an insertion sort to finish up the data.
*For partitions smaller than the cutoff size, the data is not sorted. This
*will sort the data within each partition.
*
Q9 move.l length(sp),d4 Get the length
subq.l #1,d4
ble.s done If 0 or 1 elements, done
move.l a0,a3 Set j to first element
move.l (a3)+,d1
insertloop move.l (a3)+,d2 We have j in d2 and j-1 in d1
cmp.l d1,d2
blt.s fix1
fix1ok subq.l #1,d4
beq.s done
move.l (a3)+,d1 Get next element
cmp.l d2,d1
blt.s fix2
fix2ok subq.l #1,d4
bne.s insertloop
done move.l d5,d0
movem.l (sp)+,saveregs
rts
*
* Fix the section around j.
* At the start, d2 = [j], d1 = [j-1], a3 = j+1
*
fix1 move.l -thesize(a3,a1),d0 d0 = R[j]
lea -thesize*2(a3),a2 a2 = i = j-1
fix1loop move.l (a2),thesize(a2) K[i] -> K[i+1]
move.l 0(a2,a1.l),thesize(a2,a1.l) R[i] -> R[i+1]
cmp.l -(a2),d2
blt fix1loop Continue until >= K[i]
move.l d2,thesize(a2) K[j] -> K[i+1]
move.l d0,thesize(a2,a1.l) R[j] -> R[i+1]
move.l -thesize(a3),d2 Fix the new K[j]
addq.l #1,d5
bra.s fix1ok
*
* Fix the section around j. Like above except reverse d1 and d2
* At the start, d1 = [j], d2 = [j-1], a3 = j+1
*
fix2 move.l -thesize(a3,a1),d0 d0 = R[j]
lea -thesize*2(a3),a2 a2 = i = j-1
fix2loop move.l (a2),thesize(a2) K[i] -> K[i+1]
move.l 0(a2,a1.l),thesize(a2,a1.l) R[i] -> R[i+1]
cmp.l -(a2),d1
blt fix2loop Continue until >= K[i]
move.l d1,thesize(a2) K[j] -> K[i+1]
move.l d0,thesize(a2,a1.l) R[j] -> R[i+1]
move.l -thesize(a3),d1 Fix the new K[j]
addq.l #1,d5
bra.s fix1ok
ifd ERROR
xdef _sort
endc